package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 堆排序
 * @date 2021/4/11 16:56
 */
public class HeapSort<E> extends Sort<E> {
    /**
     * 记录元素数量
     */
    private int size;

    /**
     * ① 对序列进行原地建堆（heapify）
     * ② 重复执行以下操作，直到堆的元素数量为 1
     *   交换堆顶元素与尾元素
     *   堆的元素数量减 1
     *   对 0 位置进行 1 次 siftDown 操作
     * 计算非叶子节点的个数
     * 采用自下而上的下滤方法自建堆
     * 将第一个元素放在数组的末尾
     * 然后用下滤 将数组恢复成二叉堆
     */
    @Override
    protected void sort() {
        size = array.length;

        int len = size >> 1;

        for (int j = len - 1; j >= 0; j--) {
            siftDown(j);
        }

        while (size > 1){
            swap(0,--size);
            siftDown(0);
        }
    }

    /**
     * 先计算出整棵二叉堆的非叶子节点的个数，然后进行循环
     * 每次循环 获取当前节点的左右子节点的索引，然后选取最大元素的索引，将内部元素 赋值给当前节点
     * 最后将最大元素的索引当作当前节点再次循环
     */
    private void siftDown(int index) {

        E element = array[index];
        int i = size >> 1;
        while (index < i) {
            int leftIndex = (index << 1) + 1;
            E leftElement = array[leftIndex];

            int rightIndex = leftIndex + 1;
            if (rightIndex < size && (cmpElement(array[rightIndex],leftElement) > 0)){
                leftElement = array[leftIndex = rightIndex];
            }

            if (cmpElement(element, leftElement) >= 0) {
                break;
            }
            array[index] = leftElement;
            index = leftIndex;
        }
        array[index] = element;
    }
}
